# -*- coding: utf-8 -*-

"""剑指 Offer II 015. 字符串中的所有变位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同，但排列不同的字符串。

示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。

示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的变位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的变位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的变位词。

提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母"""


class Solution:
    """此题与 z014 分析是相同的，本体用滑动窗口解决，同时注意，归还与消耗都是发现该字符在table中存在即操作，不管table中还有没有。
    因为，如果存在这种情况 <bcabac, abc> 窗口移动到 aba 时，第一个 a 已经消耗掉 table.a，第二个 a 如果不消耗的话，窗口再移一位，
    到 bac 窗口时，第一个 a 归还后，消耗掉尾部 c，ptable:={a=1, b=0, c=0}，造成错误。
    
    有效的方式为，window:=<aba>, ptable:={a=-1, b=0, c=1}  >>>窗口右移一位>>> window:=<bac>, ptable:={a=0, b=0, c=0}"""
    def findAnagrams(self, s: str, p: str):
        ptable = {}
        for c in p:
            if c in ptable.keys():
                ptable[c] += 1
            else:
                ptable[c] = 1
        
        window_size = len(p)
        try:
            for i in range(window_size):
                if s[i] in ptable.keys():
                    ptable[s[i]] -= 1
        except IndexError:
            return []
        
        locs = []
        for loc in range(len(s)-window_size+1):
            if min(ptable.values()) == 0 and max(ptable.values()) == 0:
                locs.append(loc)
            
            if s[loc] in ptable.keys():
                ptable[s[loc]] += 1
            
            try:
                tail_peek = loc+window_size
                if s[tail_peek] in ptable.keys():
                    ptable[s[tail_peek]] -= 1
            except IndexError:
                pass
        
        return locs


if __name__ == '__main__':
    so = Solution()
    print(so.findAnagrams(s = "cbaebabacd", p = "abc"))
    print(so.findAnagrams(s = "abab", p = "ab"))
    print(so.findAnagrams(s = "abacbabc", p = "abc"))
    print(so.findAnagrams(s = "aaaaaaaaaa", p = "aaaaaaaaaaaaa"))

